package com.lee.algorithm.linkedlist;

import com.lee.algorithm.linkedlist.struct.OneWayNode;

import java.util.HashSet;

/***
 * @description: 两个单链表相交（单链表、单链表、单链表）
 * @author : 青石路
 * @date: 2021/12/3 19:16
 */
public class OneWayIntersect {

    /**
     * 给定两个可能有环也可能无环的单链表，头结点head1和head2
     * 如果两个链表相交，则返回相交的第一个节点
     * 如果不相交，返回null
     *
     * 要求：如果两个链表的长度为 N，时间复杂度为 O(N)，额外空间复杂度 O(1)
     */

    /**
     * 判断是否成环，成环则返回入环的第一个节点
     * 哈希表处理
     *      链表元素逐个放入哈希表
     *      一旦某个元素存在于哈希表中，则说明成环，链表停止遍历，并且返回该元素
     *      链表遍历完，则说明未成环，返回 null
     * @author 博客园 @ 青石路
     * @param head
     * @return
     */
    public static OneWayNode getLoopNode(OneWayNode head) {
        HashSet<OneWayNode> set = new HashSet<>();
        OneWayNode cur = head;
        while (cur != null) {
            // 放入哈希表之前先判断哈希表中是否已存在
            if (set.contains(cur)) {
                return cur;     // 一旦存在则直接返回，此节点就是入环的第一个节点
            }
            set.add(cur);
            cur = cur.next;
        }

        // 链表能遍历完，则说明没有成环，直接返回 null
        return null;
    }

    /**
     * 判断是否成环，成环则返回入环的第一个节点
     * 快指针一次走两步，慢指针一次走一步
     *      如果成环，快慢指针一定会相遇于环中
     *      Floyd判圈算法
     *          如果相遇，快指针回到起点（head），慢指针停在原地
     *          然后快慢指针一次都只走一步，最终两者会相遇于入环的第一个节点
     *      不成环，则快指针一定先到null，那么直接返回 null
     *
     * @author 博客园 @ 青石路
     * @param head
     * @return
     */
    public static OneWayNode getLoopNodePlus(OneWayNode head) {
        if (head == null || head.next == null || head.next.next == null) {
            return null;
        }
        OneWayNode slow = head.next;
        OneWayNode fast = head.next.next;
        while (slow != fast) {  // 若成环，快慢指针总会相遇
            if (fast.next == null || fast.next.next == null) {  // 说明是单链表，未成环
                return null;
            }
            fast = fast.next.next;
            slow = slow.next;
        }

        // 快慢指针相遇后，快指针回到头结点
        fast = head;
        while (slow != fast) {
            // 快慢指针一次都只走一步
            slow = slow.next;
            fast = fast.next;
        }
        // 快慢指针相遇的节点就是第一个入环节点
        return slow;
    }

    /**
     * 哈希表实现
     *
     * @author 博客园 @ 青石路
     * @param h1
     * @param h2
     * @return
     */
    public static OneWayNode getIntersectNode(OneWayNode h1, OneWayNode h2) {
        if (h1 == null || h2 == null) {
            return null;
        }
        HashSet<OneWayNode> set1 = new HashSet<>();
        HashSet<OneWayNode> set2 = new HashSet<>();

        //  将链表 h1 中节点全部放入 set1
        OneWayNode cur = h1;
        while (cur != null) {
            if (set1.contains(cur)) {
                // h1 成环了，h1 节点都放入到了 set1
                break;
            }
            set1.add(cur);
            cur = cur.next;
        }

        //  将链表 h2 中节点全部放入 set2
        cur = h2;
        while (cur != null) {
            if (set2.contains(cur)) {
                // h2 成环了，h2 节点都放入到了 set2
                break;
            }
            set2.add(cur);
            cur = cur.next;
        }

        cur = h1;
        while (cur != null && !set1.isEmpty()) {
            if (set1.contains(cur) && set2.contains(cur)) {
                // 一旦找到set1、set2都包含的节点
                // 该节点即是第一个相交的节点，直接返回当前节点
                return cur;
            }
            // 遍历 h1 的同时，从 set1 中移除当前节点
            set1.remove(cur);
            cur = cur.next;
        }

        // 不相交返回 null
        return null;
    }

    /**
     * 1) h1、h2 都未成环
     *      1.1 h1与h2不相交
     *      1.2 h1与h2相交，从第一个相交节点开始，后面的节点都是共用的
     *                n1 -> n2 -> n3 -> n4
     *          nc -> na -> nb -> n3 -> n4
     *          两个链表都从头遍历到尾（记录各自的长度 l1、l2），end1 == end2 ? 相交 : 不相交
     *          相交的话，则用长的l减去短的l = lm，长的先遍历 lm，
     *          然后两个链表同时开始遍历，一旦 n1 == n2，那么 n1（n2）就是第一个相交的节点
     *
     * 2) 一个成环，一个不成环
     *      不可能相交
     *
     * 3) 两个都成环
     *      先找到两个环的入环节点：loop1、loop2
     *      3.1) 不相交
     *          loop1 沿着环遍历一次，若没遇到 loop2，直接返回 null
     *
     *      3.2) 相交，共用入环节点
     *          此时 loop1 等于 loop2
     *          h1 ~ loop1，h2 ~ loop1，回到了 noLoop 的情况
     *
     *      3.2) 相交，不共用入环节点
     *          loop1 沿着环遍历一次，若遇到 loop2，则返回 loop1 或 loop2
     *
     * @author 博客园 @ 青石路
     * @param h1
     * @param h2
     * @return
     */
    public static OneWayNode getIntersectNodePlus(OneWayNode h1, OneWayNode h2) {
        OneWayNode loop1 = getLoopNodePlus(h1);
        OneWayNode loop2 = getLoopNodePlus(h2);

        // 1) h1、h2 都未成环
        if (loop1 == null && loop2 == null) {
            return noLoop(h1, h2);
        }

        // 3) 两个都成环
        if (loop1 != null && loop2 != null) {
            return bothLoop(h1, loop1, h2, loop2);
        }

        return null;
    }

    /**
     * h1、h2 都未成环
     *
     * @author 博客园 @ 青石路
     * @param h1
     * @param h2
     * @return
     */
    public static OneWayNode noLoop(OneWayNode h1, OneWayNode h2) {
        if (h1 == null || h2 == null) {
            return null;
        }
        OneWayNode cur1 = h1;
        OneWayNode cur2 = h2;
        int n = 0;  // 用来判断哪个链表更长
        // 寻找 h1、h2 的尾节点
        while (cur1.next != null) {
            n++;
            cur1 = cur1.next;
        }
        while (cur2.next != null) {
            n--;
            cur2 = cur2.next;
        }

        // 此时cur1 是 h1 的尾节点，cur2 是 h2 的尾节点
        if (cur1 != cur2) { // 两个链表的尾节点都不是同一个节点，肯定不相交
            return null;
        }

        // 相交，找相交的第一个节点
        cur1 = n > 0 ? h1 : h2;         // cur1 指向长链表的head
        cur2 = cur1 == h1 ? h2 : h1;    // cur2 指向短链表的head
        n  = Math.abs(n);
        // 长的链表先移动 n 个节点
        while (n != 0) {
            n--;
            cur1 = cur1.next;
        }
        // 两个链表同时移动，一次移动一步
        while(cur1 != cur2) {   // cur1 与 cur2 不是同一个节点，继续往后移动
            cur1 = cur1.next;
            cur2 = cur2.next;
        }
        // 一旦 cur1 与 cur2 是同一个节点，直接返回该节点
        return cur1;
    }

    /**
     * h1、h2都成环
     *
     * @author 博客园 @ 青石路
     * @param h1
     * @param loop1 h1的第一个入环节点
     * @param h2
     * @param loop2 h2的第一个入环节点
     * @return
     */
    public static OneWayNode bothLoop(OneWayNode h1, OneWayNode loop1, OneWayNode h2, OneWayNode loop2) {
        OneWayNode cur1 = null;
        OneWayNode cur2 = null;

        if (loop1 == loop2) {  // 3.2) 相交，共用入环节点
            cur1 = h1;
            cur2 = h2;
            int n = 0;
            // h1 ~ loop1 看成单链表
            while (cur1 != loop1) {
                n++;
                cur1 = cur1.next;
            }
            // h2 ~ loop2 看成单链表
            while (cur2 != loop2) {
                n--;
                cur2 = cur2.next;
            }
            cur1 = n > 0 ? h1 : h2;
            cur2 = cur1 == h1 ? h2 : h1;
            n = Math.abs(n);
            while(n != 0) {
                n--;
                cur1 = cur1.next;
            }
            while (cur1 != cur2) {
                cur1 = cur1.next;
                cur2 = cur2.next;
            }
            return cur1;
        } else {
            cur1 = loop1.next;
            while (cur1 != loop1) {
                if (cur1 == loop2) {    // 3.3) 相交，不共用入环节点
                    return loop1;       // return loop2; 也行
                }
                cur1 = cur1.next;
            }

            // 3.1) 不相交
            return null;
        }
    }

    public static void main(String[] args) {
        OneWayNode h1 = new OneWayNode("abc");
        OneWayNode h2 = new OneWayNode("123");
        OneWayNode n1 = new OneWayNode("n1");
        OneWayNode n2 = new OneWayNode("n2");
        OneWayNode n3 = new OneWayNode("n3");

        h1.next = n1;
        n1.next = n2;
        n2.next = n3;

        h2.next = n1;

        OneWayNode oneWayNode = noLoop(h1, h2);
        System.out.println(oneWayNode == null ? "不相交" : oneWayNode.value);
    }
}
